#include <iostream>
#include <climits>
#include <string>
#include <algorithm>
#include <stdexcept>

using namespace std;

typedef enum
{
    Link,
    Thread
} NodeTag;

class TreeNode
{
private:
    char data;            // 值
    TreeNode *leftChild;  // 左孩子
    TreeNode *rightChild; // 右孩子
    NodeTag lTag, rTag;   // 线索Tag

    friend class MyTree; // 树类
public:
    TreeNode(char, TreeNode *, TreeNode *, NodeTag, NodeTag);
    TreeNode();
    ~TreeNode();

    void printNode();
};

class MyTree
{
private:
    TreeNode *root; // 根指针
    bool isThread;  // 线索二叉树标志
public:
    MyTree();               // 无参构造
    MyTree(const char[]);   // 构造函数
    MyTree(const MyTree &); // 拷贝函数
    ~MyTree();              // 析构函数
    TreeNode *generateTree(const char pre[], int &index);
    TreeNode *copyTree(const TreeNode *T);
    void destroyTree(TreeNode *node);
    void preOrderTraverse();     // 前序遍历
    void preorder(TreeNode *p);  // 前序遍历辅助函数
    void inOrderTraverse();      // 中序遍历
    void inorder(TreeNode *p);   // 中序遍历辅助函数
    void postOrderTraverse();    // 后序遍历
    void postorder(TreeNode *p); // 后序遍历辅助函数
    int countLeaf();             // 叶结点计数
    int numleaf(TreeNode *p);    // 叶子节点级数辅助函数
    int countHeight();           // 计算树的深度
    int Height(TreeNode *p);
    bool isThreadedTree();   // 判断是否为线索二叉树
    bool inOrderThreading(); // 线索化
    void threading(TreeNode *p);
    TreeNode &locateNode(const char &); // 结点定位
    TreeNode *locate(const char &a, TreeNode *p);
    TreeNode &preNode(const TreeNode &);  // 获取前驱结点
    TreeNode &nextNode(const TreeNode &); // 获取后继结点
};

class HuffmanTree
{
private:
    // 添加必要的数据成员
    // myadd
    class HFNode
    {
    public:
        int left, right;
        // -1表示无父节点
        int parent;
        int weight;
        string code;
    } *HFT;
    int num;

public:
    HuffmanTree(const int &, const int[]); // 构造函数
    ~HuffmanTree();                        // 析构函数

    // 输出哈夫曼编码
    // 格式为：每行输出一个节点，节点排序递减
    // 节点1值：编码
    // 节点2值：编码
    //....
    // cpp中未给出该函数，遵守输出格式规范
    void printHuffmanCodes();

    // add
    void selectMin(HFNode *hft, int n, int &s1, int &s2);
    void initleaves(int n, const int *data);

    void generateCodes(int idx, string code);
};